public class Solution {
    //不用加号的加法
    public int add(int a, int b) {
        //0 + 0 = 0
        //0 + 1 = 1
        //1 + 0 = 1
        //1 + 1 = 10
        // 计算a+b不包含进位
        int sum = a ^ b;
        //计算进位
        int t = (a&b)<<1;
        while (t != 0) {
            //加上进位
            int tmp = sum^t;
            //计算新的进位
            t = (sum&t)<<1;
            //更新和
            sum = tmp;
        }
        return sum;
    }
    //乘积为正数的最长子数组长度
    public int getMaxLen(int[] nums) {
        int n = nums.length;
        int[] f = new int[n+1];
        int[] g = new int[n+1];
        //增加虚拟节点，不影响填表值
        f[0] = 0;
        g[0] = 0;
        int max = Integer.MIN_VALUE;
        for(int i = 1; i <= n; i++) {
            if(nums[i-1] > 0) {
                f[i] = f[i-1]+1;
                g[i] = g[i-1]==0? 0 : g[i-1]+1;
            }
            if(nums[i-1] < 0) {
                f[i] = g[i-1]==0? 0 : g[i-1]+1;
                g[i] = f[i-1]+1;
            }
            if(f[i] > max) {
                max = f[i];
            }
        }
        return max;
    }
    //等差数列划分
    public int numberOfArithmeticSlices(int[] nums) {
        int n = nums.length;
        //dp[i]表示i个位置的子等差数列数
        int[] dp = new int[n];
        dp[0] = 0;
        if(n == 1) {
            return dp[0];
        }
        dp[1] = 0;
        int sum = 0;
        for(int i = 2; i < n ; i++) {
            dp[i] = nums[i] - nums[i-1] == nums[i-1] - nums[i-2] ? dp[i-1]+1 : 0;
            sum += dp[i];
        }
        return sum;
    }
}
